package com.heima.leetcode.practice;

import java.util.Arrays;

/**
 * leetcode 14. 最长公共前缀
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/27 9:50
 */
public class E14 {

    /**
     * <h3>方法一：最小公共长度内挨个判断</h3>
     * @param tokens 指定字符串数组
     * @return 最长公共前缀
     */
    public String longestCommonPrefix1(String[] tokens) {
        StringBuilder builder = new StringBuilder();
        // 最小长度
        int minLength = tokens[0].length();
        for (int i = 1; i < tokens.length; i++) {
            int length = tokens[i].length();
            if (length < minLength) {
                minLength = length;
            }
        }
        // 挨个判断
        for (int i = 0; i < minLength; i++) {
            if (equalsCurrentIndex(tokens, i)) {
                builder.append(tokens[0].charAt(i));
            } else {
                break;
            }
        }
        return builder.toString();
    }

    /**
     * 判断当前位置是否相等
     * @param tokens 指定字符串数组
     * @param index  指定位置
     * @return 相等返回true，否则返回false
     */
    private boolean equalsCurrentIndex(String[] tokens, int index) {
        char current = tokens[0].charAt(index);
        for (int i = 1; i < tokens.length; i++) {
            if (current != tokens[i].charAt(index)) {
                return false;
            }
        }
        return true;
    }

    /**
     * <h3>方法二：水平扫描法，适合小规模数据</h3>
     * @param tokens 指定字符串数组
     * @return 最长公共前缀
     */
    public String longestCommonPrefix2(String[] tokens) {
        // if (tokens == null || tokens.length == 0){
        //     return "";
        // }
        String prefix = tokens[0]; // 将第一个作为前缀
        for (int i = 1; i < tokens.length; i++) {
            while (tokens[i].indexOf(prefix) != 0){ // 前缀所在位置的索引不是0
                prefix = prefix.substring(0, prefix.length() - 1); //则截取前缀
                if (prefix.isEmpty()){ // 被截取没了
                    return "";
                }
            }
        }
        return prefix;
    }

    /**
     * <h3>方法三：纵向扫描法，适合小规模数据</h3>
     * @param tokens 指定字符串数组
     * @return 最长公共前缀
     */
    public String longestCommonPrefix3(String[] tokens) {
        // if (tokens == null || tokens.length == 0){
        //     return "";
        // }
        // 思路将第一个字符串的每一个位置与后面的字符串挨个比较，比较过程要保证不能越界
        for (int i = 0; i < tokens[0].length(); i++) {
            // 当前需要确认的第i位字符
            char target = tokens[0].charAt(i);
            for (int j = 1; j < tokens.length; j++){
                // 比较后面的每一个字符串的第i位是否为这个字符，首先前提就是够这么多字符
                // 当前已经确认的最长前缀(0 - i-1),当比较第i位的时候发现tokens[j]的长度为i，也就是tokens[j]只存在i-1个字符，则会越界
                if (tokens[j].length() == i || tokens[j].charAt(i) != target){
                    // 当第一个位置就不一样时能处理substring(0, 0)的结果就是""
                    return tokens[0].substring(0, i);
                }
            }
        }
        // 处理完了tokens[0]的每一位，而且都是满足的
        return tokens[0];
    }

    /**
     * <h3>方法四：分而治之，适合大规模数据，具有良好的扩展性</h3>
     * @param tokens 指定字符串数组
     * @return 最长公共前缀
     */
    public String longestCommonPrefix4(String[] tokens) {
        // if (tokens == null || tokens.length == 0){
        //     return "";
        // }
       return longestCommonPrefix4(tokens, 0, tokens.length - 1);
    }

    /**
     * 分而治之实现
     * @param tokens 字符串数组
     * @param begin 开始索引（包含）
     * @param end 结束索引（包含）
     * @return 字符串数组开始索引到结束索引内的最长公共前缀
     */
    private String longestCommonPrefix4(String[] tokens, int begin, int end) {
        // 递归结束条件：字符串数组里面只有一个字符串
        if (begin == end){
            return tokens[begin];
        }
        // 将tokens字符串数组分成均匀两部分
        // 递的时候求取左右两边的公共前缀
        int median = (begin + end) >>> 1;
        String leftPrefix = longestCommonPrefix4(tokens, begin, median);
        String rightPrefix = longestCommonPrefix4(tokens, median + 1, end);
        // 归的时候将两边的公共前缀合并成一个新的前缀
        return commonPrefix(leftPrefix, rightPrefix);
    }

    /**
     * 合并左右两个前缀，实际就是公共部分抽取出来
     * @param leftPrefix 左部分前缀
     * @param rightPrefix 有部分前缀
     * @return 新的公共前缀
     */
    private String commonPrefix(String leftPrefix, String rightPrefix) {
        int minLength = Math.min(leftPrefix.length(), rightPrefix.length());
        for (int i = 0; i < minLength; i++) {
            if (leftPrefix.charAt(i) != rightPrefix.charAt(i)){
                return leftPrefix.substring(0, i);
            }
        }
        return leftPrefix.substring(0, minLength);
    }

    /**
     * <h3>方法五：字典树，对于大量字符串的公共前缀查询效率高，但实现较为复杂。</h3>
     * @param tokens 指定字符串数组
     * @return 最长公共前缀
     */
    public String longestCommonPrefix5(String[] tokens) {
        Trie trie = new Trie();
        for (String token : tokens) {
            trie.insert(token);
        }
        return trie.longestPrefix();
    }

    /**
     * <h3>方法六：排序法，时间复杂度较高</h3>
     * @param tokens 指定字符串数组
     * @return 最长公共前缀
     */
    public String longestCommonPrefix6(String[] tokens) {
        // if (tokens == null || tokens.length == 0) {
        //     return "";
        // }
        // 排序字符串数组
        Arrays.sort(tokens);
        // 获取排序后的第一个和最后一个字符串
        String first = tokens[0];
        String last = tokens[tokens.length - 1];
        int minLength = Math.min(first.length(), last.length());
        int i = 0;
        // 比较两个字符串的字符
        while (i < minLength && first.charAt(i) == last.charAt(i)) {
            i++;
        }
        // 返回最长公共前缀
        return first.substring(0, i);
    }
}
